{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Closed Islands"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closedIsland"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计封闭岛屿的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>二维矩阵 <code>grid</code>&nbsp;由 <code>0</code>&nbsp;（土地）和 <code>1</code>&nbsp;（水）组成。岛是由最大的4个方向连通的 <code>0</code>&nbsp;组成的群，封闭岛是一个&nbsp;<code>完全</code> 由1包围（左、上、右、下）的岛。</p>\n",
    "\n",
    "<p>请返回 <em>封闭岛屿</em> 的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/10/31/sample_3_1610.png\" style=\"height: 151px; width: 240px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/11/07/sample_4_1610.png\" style=\"height: 98px; width: 160px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1,1,1,1,1,1],\n",
    "&nbsp;            [1,0,0,0,0,0,1],\n",
    "&nbsp;            [1,0,1,1,1,0,1],\n",
    "&nbsp;            [1,0,1,0,1,0,1],\n",
    "&nbsp;            [1,0,1,1,1,0,1],\n",
    "&nbsp;            [1,0,0,0,0,0,1],\n",
    "             [1,1,1,1,1,1,1]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= grid.length, grid[0].length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;=1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-closed-islands](https://leetcode.cn/problems/number-of-closed-islands/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-closed-islands](https://leetcode.cn/problems/number-of-closed-islands/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]', '[[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]', '[[1,1,1,1,1,1,1],[1,0,0,0,0,0,1],[1,0,1,1,1,0,1],[1,0,1,0,1,0,1],[1,0,1,1,1,0,1],[1,0,0,0,0,0,1],[1,1,1,1,1,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, a: List[List[int]]) -> int:\n",
    "        n,m = len(a),len(a[0])\n",
    "        b = [[0]*m for i in range(n)]\n",
    "        cnt = 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if a[i][j]==0:\n",
    "                    b[i][j] = cnt\n",
    "                    cnt+=1\n",
    "        \n",
    "        f = [i for i in range(cnt)]\n",
    "\n",
    "        def get(x):\n",
    "            if x!=f[x]:\n",
    "                f[x] = get(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def merge(x,y):\n",
    "            xx,yy = get(x),get(y)\n",
    "            if xx != yy:\n",
    "                f[xx]=yy\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if a[i][j]==1:\n",
    "                    continue\n",
    "                for di, dj in [[-1,0],[1,0],[0,-1],[0,1]]:\n",
    "                    ii=i+di\n",
    "                    jj=j+dj\n",
    "\n",
    "                    if ii<0 or ii>=n or jj<0 or jj>=m:\n",
    "                        # print(i,j,ii,jj)\n",
    "                        merge(0, b[i][j])\n",
    "                    else:\n",
    "                        if b[ii][jj] > 0:\n",
    "                            # print(i,j,ii,jj)\n",
    "                            merge(b[i][j],b[ii][jj])\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if b[i][j] > 0:\n",
    "                    ans.append(get(b[i][j]))\n",
    "        c = get(0)\n",
    "        ans = set(ans)\n",
    "        if c not in ans:\n",
    "            return len(set(ans))\n",
    "        else:\n",
    "            return len(set(ans))-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, len(grid) - 1):\n",
    "            for j in range(1, len(grid[0]) - 1):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += self.dfs(grid, i, j)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, grid, i, j):\n",
    "        a = len(grid) - 1\n",
    "        b = len(grid[0]) - 1\n",
    "        stack = [(i, j)]\n",
    "        res = 1\n",
    "        while stack:\n",
    "            x, y = stack.pop()\n",
    "            grid[x][y] = -1\n",
    "            if x - 1 >= 0 and grid[x-1][y] == 0:\n",
    "                stack.append((x-1, y))\n",
    "                grid[x - 1][y] = -1\n",
    "                if x - 1 == 0:\n",
    "                    res = 0\n",
    "            if x + 1 <= a and grid[x + 1][y] == 0:\n",
    "                stack.append((x+1, y))\n",
    "                grid[x + 1][y] = -1\n",
    "                if x + 1 == a:\n",
    "                    res = 0\n",
    "            if y - 1 >= 0 and grid[x][y-1] == 0:\n",
    "                stack.append((x, y-1))\n",
    "                grid[x][y-1] = -1\n",
    "                if y - 1 == 0:\n",
    "                    res = 0\n",
    "            if y + 1 <= b and grid[x][y+1] == 0:\n",
    "                stack.append((x, y+1))\n",
    "                grid[x][y+1] = -1\n",
    "                if y + 1 == b:\n",
    "                    res = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid) -> int:\n",
    "        d = [0, 1, 0, -1, 0]\n",
    "        for x in range(len(grid)):\n",
    "            for y in [0, len(grid[0])-1]:\n",
    "                if grid[x][y] == 0:\n",
    "                    grid[x][y] = 1\n",
    "                    self.to_1(grid, x, y, d)\n",
    "\n",
    "        for y in range(len(grid[0])):\n",
    "            for x in [0, len(grid) -1]:\n",
    "                if grid[x][y] == 0:\n",
    "                    grid[x][y] = 1\n",
    "                    self.to_1(grid, x, y, d)\n",
    "        ans = 0\n",
    "        for x in range(len(grid)):\n",
    "            for y in range(len(grid[0])):\n",
    "                if grid[x][y] == 0:\n",
    "                    ans += 1\n",
    "                    grid[x][y] = 1\n",
    "                    self.to_1(grid, x, y, d)\n",
    "        return ans\n",
    "\n",
    "    def to_1(self, grid, x, y, d):\n",
    "        for i in range(4):\n",
    "            nx, ny = x + d[i], y + d[i + 1]\n",
    "            if nx >= 0 and ny >= 0 and nx < len(grid) and ny < len(grid[0]) and not grid[nx][ny]:\n",
    "                grid[nx][ny] = 1\n",
    "                self.to_1(grid, nx, ny, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "    def closedIsland(self, grid):\n",
    "        ans = 0\n",
    "        self.grid = grid\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    self.val = 1\n",
    "                    self.dfs(i, j)\n",
    "                    ans += self.val\n",
    "        return ans\n",
    "    def dfs(self, i, j):\n",
    "        if not all([0 <= i < len(self.grid), 0 <= j < len(self.grid[0])]):\n",
    "            self.val = 0\n",
    "            return 0\n",
    "        if self.grid[i][j] != 0: return\n",
    "        self.grid[i][j] = -1\n",
    "        for d in self.directions:\n",
    "            di = i + d[0]\n",
    "            dj = j + d[1]\n",
    "            self.dfs(di, dj)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    directions = [(-1, 0), (0, -1) ,(1, 0), (0, 1)]\n",
    "    def markAs3(self, grid, i, j):\n",
    "        grid[i][j] = 2\n",
    "        for d in self.directions:\n",
    "            di = i + d[0]\n",
    "            dj = j + d[1]\n",
    "            if all([0 < di < self.rl - 1, 0 < dj < self.cl - 1]) and grid[di][dj] == 0:\n",
    "                self.markAs3(grid, di, dj)\n",
    "    def closedIsland(self, grid):\n",
    "        self.rl = len(grid)\n",
    "        self.cl = len(grid[0])\n",
    "        for j in range(self.cl):\n",
    "            if grid[0][j] == 0:\n",
    "                self.markAs3(grid, 0, j)\n",
    "            if grid[self.rl - 1][j] == 0:\n",
    "                self.markAs3(grid, self.rl - 1, j)\n",
    "        for i in range(self.rl):\n",
    "            if grid[i][0] == 0:\n",
    "                self.markAs3(grid, i, 0)\n",
    "            if grid[i][self.cl - 1] == 0:\n",
    "                self.markAs3(grid, i, self.cl - 1)\n",
    "        count = 0\n",
    "        for i in range(self.rl):\n",
    "            for j in range(self.cl):\n",
    "                if grid[i][j] == 0:\n",
    "                    self.markAs3(grid, i, j)\n",
    "                    count += 1\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        island_count = 0\n",
    "        for i in range(1, len(grid) - 1):\n",
    "            for j in range(1, len(grid[0]) - 1):\n",
    "                if grid[i][j] == 0:\n",
    "                    is_island = [True]\n",
    "                    self.traverse(grid, i, j, is_island)\n",
    "                    if is_island[0]:\n",
    "                        island_count += 1\n",
    "        return island_count\n",
    "\n",
    "    def traverse(self, grid, i, j, is_island):\n",
    "        if grid[i][j] == 1:\n",
    "            return\n",
    "        grid[i][j] = 1\n",
    "        if i == 0 or j == 0 or i == len(grid) - 1 or j == len(grid[0]) - 1:\n",
    "            is_island[0] = False\n",
    "        if i - 1 >= 0 and grid[i - 1][j] == 0:\n",
    "            self.traverse(grid, i - 1, j, is_island)\n",
    "        if j - 1 >= 0 and grid[i][j - 1] == 0:\n",
    "            self.traverse(grid, i, j - 1, is_island)\n",
    "        if i + 1 < len(grid) and grid[i + 1][j] == 0:\n",
    "            self.traverse(grid, i + 1, j, is_island)\n",
    "        if j + 1 < len(grid[0]) and grid[i][j + 1] == 0:\n",
    "            self.traverse(grid, i, j + 1, is_island)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dire = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        rows,cols=len(grid),len(grid[0])\n",
    "        res=0\n",
    "        for j in range(cols):\n",
    "            if grid[0][j]==0:\n",
    "                self.dfs(grid,0,j)\n",
    "            if grid[rows-1][j]==0:\n",
    "                self.dfs(grid,rows-1,j)\n",
    "        for i in range(rows):\n",
    "            if grid[i][0]==0:\n",
    "                self.dfs(grid,i,0)\n",
    "            if grid[i][cols-1]==0:\n",
    "                self.dfs(grid,i,cols-1)\n",
    "        for i in range(1,rows-1):\n",
    "            for j in range(1,cols-1):\n",
    "                if grid[i][j]==0:\n",
    "                    res+=1\n",
    "                    self.dfs(grid,i,j)\n",
    "        return res\n",
    "    def dfs(self,grid,x,y):\n",
    "        rows,cols=len(grid),len(grid[0])\n",
    "        grid[x][y]=1\n",
    "        for i in range(4):\n",
    "            r,c=x+self.dire[i][0],y+self.dire[i][1]\n",
    "            if r>=0 and r<rows and c>=0 and c<cols:\n",
    "                if grid[r][c]==0:\n",
    "                    self.dfs(grid,r,c)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        def dfs(grid, i, j):\n",
    "            if grid[i][j] == 1:\n",
    "                return\n",
    "            direction = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            grid[i][j] = 1\n",
    "            for x, y in direction:\n",
    "                if 0 <= i+x < r and 0 <= j+y < c and grid[i+x][j+y] == 0:\n",
    "                    dfs(grid, i+x, j+y)\n",
    "            \n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        \n",
    "        count = 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if i == 0 or i == r-1 or j == 0 or j == c-1:\n",
    "                    if grid[i][j] == 0:\n",
    "                        dfs(grid, i, j)\n",
    "    #     print(grid)   \n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == 0:\n",
    "                    count += 1\n",
    "                    dfs(grid, i, j)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(grid,i,j):\n",
    "            if i<0 or i>=m or j<0 or j>=n:\n",
    "                return False # 到达边界，非封闭\n",
    "            if grid[i][j] != 0:\n",
    "                return True\n",
    "            grid[i][j]=2\n",
    "            up = dfs(grid,i-1,j);\n",
    "            down = dfs(grid,i+1,j);\n",
    "            left = dfs(grid,i,j-1);\n",
    "            right = dfs(grid,i,j+1);\n",
    "            return up and down and left and right\n",
    "            # return dfs(grid,i-1,j) && dfs(grid,i+1,j) && dfs(grid,i,j-1) && dfs(grid,i,j+1)\n",
    "\n",
    "        if not grid or len(grid[0])==0:\n",
    "            return 0\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        count=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    if dfs(grid,i,j):\n",
    "                        count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        #染色函数\n",
    "        def fun(x,y):\n",
    "            if grid[x][y]==0:\n",
    "                grid[x][y]=1\n",
    "                if x+1<len(grid):fun(x+1,y)\n",
    "                if x-1>=0:fun(x-1,y)\n",
    "                if y+1<len(grid[0]):fun(x,y+1)\n",
    "                if y-1>=0:fun(x,y-1)\n",
    "        #染色边界\n",
    "        for x in range(len(grid)):\n",
    "            fun(x,0)\n",
    "            fun(x,len(grid[0])-1)\n",
    "        for y in range(len(grid[0])):\n",
    "            fun(0,y)\n",
    "            fun(len(grid)-1,y)\n",
    "        #染色中间并计数\n",
    "        res=0\n",
    "        for x in range(len(grid)):\n",
    "            for y in range(len(grid[x])):\n",
    "                if grid[x][y]==0:\n",
    "                    fun(x,y)\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        M = len(grid)\n",
    "        N = len(grid[0])\n",
    "        ans = 0\n",
    "        def dfs(x,y):\n",
    "            grid[x][y] = 1\n",
    "            for i, j in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:\n",
    "                if 0<=i<M and 0<=j<N and grid[i][j] == 0:\n",
    "                    dfs(i,j)\n",
    "        for i in range(M):\n",
    "            if grid[i][0] == 0:\n",
    "                dfs(i,0)\n",
    "            if grid[i][N-1] ==0:\n",
    "                dfs(i,N-1)\n",
    "        for j in range(N):\n",
    "            if grid[0][j] == 0:\n",
    "                dfs(0,j)\n",
    "            if grid[M-1][j] == 0:\n",
    "                dfs(M-1,j)\n",
    "        for i in range(1,M-1):\n",
    "            for j in range(1,N-1):\n",
    "                \n",
    "                  if grid[i][j] == 0:\n",
    "                            ans += 1\n",
    "                            dfs(i,j)\n",
    "        return ans\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        seen = [[False for _ in range(m)]for _ in range(n)]\n",
    "        res = 0\n",
    "        self.valid = True\n",
    "        \n",
    "        def dfs(x,y):\n",
    "            if x==0 or x==n-1 or y==0 or y==m-1: self.valid = False\n",
    "            seen[x][y] =True\n",
    "            for dx,dy in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)):\n",
    "                if 0<=dx<n and 0<=dy<m and not seen[dx][dy] and grid[dx][dy]==0:\n",
    "                    dfs(dx,dy)\n",
    "        \n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                if grid[x][y]==0 and not seen[x][y]:\n",
    "                    dfs(x,y)\n",
    "                    if self.valid: res+=1\n",
    "                    self.valid = True\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        c, r = len(grid), len(grid[0])\n",
    "        tmp = [0] * r\n",
    "        grid.insert(0, tmp)\n",
    "        grid.append(tmp)\n",
    "        c, r = c + 2, r + 2\n",
    "        for k in range(1, c):\n",
    "            grid[k].insert(0, 0)\n",
    "            grid[k].append(0)\n",
    "\n",
    "        dirs = {(1, 0), (0, 1), (-1, 0), (0, -1)}\n",
    "        visited = [[False] * r for _ in range(c)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            visited[i][j] = True\n",
    "            for item in dirs:\n",
    "                x = i + item[0]\n",
    "                y = j + item[1]\n",
    "                if x < 0 or x >= c or y < 0 or y >= r or visited[x][y]:\n",
    "                    continue\n",
    "                if grid[x][y] == 0:\n",
    "                    dfs(x, y)\n",
    "\n",
    "        result = 0\n",
    "        for u in range(c):\n",
    "            for v in range(r):\n",
    "                if visited[u][v] or grid[u][v] == 1:\n",
    "                    continue\n",
    "                dfs(u, v)\n",
    "                result += 1\n",
    "\n",
    "        return result - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\" BFS \"\"\"\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def bfs(i: int, j: int) -> bool:\n",
    "            \"\"\" 广度优先搜索某一个岛屿中的所有陆地 \"\"\"\n",
    "            queue = [(i, j)]\n",
    "            is_closed = True\n",
    "            while queue:\n",
    "                x, y = queue.pop(0)\n",
    "                if not (0 <= x < m and 0 <= y < n):\n",
    "                    is_closed = False\n",
    "                elif grid[x][y] != 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    grid[x][y] = 2\n",
    "                    queue.extend([\n",
    "                        (x - 1, y),\n",
    "                        (x + 1, y),\n",
    "                        (x, y - 1),\n",
    "                        (x, y + 1)\n",
    "                    ])\n",
    "            return is_closed\n",
    "\n",
    "        num = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and bfs(i, j):\n",
    "                    num += 1\n",
    "        return num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1254 lang=python3\n",
    "#\n",
    "# [1254] 统计封闭岛屿的数目\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "from typing import List \n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        # 思路1：先找陆地0，再沿着陆地0向外扩展一圈，看看是否都是海（要排除边界）\n",
    "        # 思路2：先找所有的岛屿（联通的0），再把边上的岛屿去掉（把0变成1）\n",
    "\n",
    "        def dfs(grid, x, y):\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                return  # 过了边界\n",
    "            if grid[x][y] == 1:  # 是海洋就跳过\n",
    "                return \n",
    "            grid[x][y] = 1  # 被海水淹没，（来过一次）\n",
    "            dfs(grid, x - 1, y)\n",
    "            dfs(grid, x, y - 1)\n",
    "            dfs(grid, x + 1, y)\n",
    "            dfs(grid, x, y + 1)\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 把边上的岛屿去掉\n",
    "        for i in range(m):  # 从上到下检查左右边界\n",
    "            dfs(grid, i, 0 )\n",
    "            dfs(grid, i, n-1)\n",
    "        for i in range(n): # 从左到右检查上下边界\n",
    "            dfs(grid, 0, i)\n",
    "            dfs(grid, m-1, i)\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "                    dfs(grid, i, j)\n",
    "        return res\n",
    "\n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        def dfs(i,j,grid):\n",
    "            if not 0<=i<m or not 0<=j<n:\n",
    "                return False\n",
    "            if grid[i][j] == 1:\n",
    "                return True\n",
    "            grid[i][j] = 1\n",
    "            top = dfs(i-1,j,grid)\n",
    "            bottom = dfs(i+1,j,grid)\n",
    "            left = dfs(i,j-1,grid)\n",
    "            right = dfs(i,j+1,grid)\n",
    "            return top and bottom and left and right\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    isClosed = dfs(i,j,grid)\n",
    "                    if isClosed:\n",
    "                        res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(grid, r, c):\n",
    "            if not 0<=r<len(grid) or not 0<=c<len(grid[0]):\n",
    "                self.flag=0\n",
    "                return\n",
    "            if grid[r][c] != 0:\n",
    "                return\n",
    "            grid[r][c] = 1\n",
    "            dfs(grid, r - 1, c)\n",
    "            dfs(grid, r + 1, c)\n",
    "            dfs(grid, r, c - 1)\n",
    "            dfs(grid, r, c + 1)\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    self.flag=1\n",
    "                    dfs(grid, i, j)\n",
    "                    res += self.flag\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIslandDFS(self, grid, i, j, m, n):\n",
    "        # 越界直接退出\n",
    "        if i < 0 or i >= m or j < 0 or j >= n:\n",
    "            return\n",
    "        # 遇到0也直接退出\n",
    "        if grid[i][j] == 1:\n",
    "            return\n",
    "        # 添加当前节点\n",
    "        grid[i][j] = 1\n",
    "        # 向上下左右四个方向开始遍历\n",
    "        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "            self.closedIslandDFS(grid, i + dx, j + dy, m, n)\n",
    "\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        # 利用广度遍历解决\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m < 3 or n < 3:\n",
    "            return 0\n",
    "        # 先遍历四周一圈，将所有的0置为1\n",
    "        for i in range(m):\n",
    "            if grid[i][0] == 0:\n",
    "                # 进行深度遍历\n",
    "                self.closedIslandDFS(grid, i, 0, m, n)\n",
    "            if grid[i][n - 1] == 0:\n",
    "                # 进行深度遍历\n",
    "                self.closedIslandDFS(grid, i, n - 1, m, n)\n",
    "        for j in range(1, n - 1):\n",
    "            if grid[0][j] == 0:\n",
    "                # 进行深度遍历\n",
    "                self.closedIslandDFS(grid, 0, j, m, n)\n",
    "            if grid[m - 1][j] == 0:\n",
    "                # 进行深度遍历\n",
    "                self.closedIslandDFS(grid, m - 1, j, m, n)\n",
    "        res = 0\n",
    "        # 遍历内环\n",
    "        for i in range(1, m - 1):\n",
    "            for j in range(1, n - 1):\n",
    "                if grid[i][j] == 0:\n",
    "                    # 深度遍历周围的数据\n",
    "                    self.closedIslandDFS(grid, i, j, m, n)\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i,j,id):\n",
    "            nonlocal tag\n",
    "            for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "                x = i+dx\n",
    "                y = j+dy\n",
    "                if 0<=x<=m-1 and 0<=y<=n-1:\n",
    "                    if p[x][y] == 0:\n",
    "                        p[x][y] = id\n",
    "                        dfs(x,y,id)\n",
    "                    elif p[x][y] == -1:\n",
    "                        tag = 1\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        p = [[0 for _ in range(n)]for _ in range(m)]\n",
    "        id = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    p[i][j] = 1\n",
    "                elif i in [0,m-1] or j in [0,n-1]:\n",
    "                    p[i][j] = -1\n",
    "        num = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if p[i][j] == 0:\n",
    "                    id += 1\n",
    "                    p[i][j] = id\n",
    "                    tag = 0\n",
    "                    dfs(i,j,id)\n",
    "                    if not tag:\n",
    "                        num += 1\n",
    "        return num\n",
    "\n",
    "                        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        \n",
    "        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        H = len(grid)\n",
    "        W = len(grid[0])\n",
    "        visited = [[False] * W for _ in range(H)]\n",
    "        res = 0\n",
    "        def traverse(row, col):\n",
    "            if row not in range(H) or col not in range(W):\n",
    "                return False\n",
    "            \n",
    "            if visited[row][col]:\n",
    "                return True\n",
    "            \n",
    "            if grid[row][col] == 1:\n",
    "                return True\n",
    "            \n",
    "            visited[row][col] = True\n",
    "\n",
    "            closed = True\n",
    "            for dr, dc in directions:\n",
    "                surrounded = traverse(row + dr, col + dc)\n",
    "                closed = closed and surrounded\n",
    "            return closed\n",
    "        \n",
    "        for i in range(H):\n",
    "            for j in range(W):\n",
    "                if grid[i][j] == 0 and not visited[i][j]:\n",
    "                    if (traverse(i, j)):\n",
    "                        res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def bfs(i, j):\n",
    "            q = [(i, j)]\n",
    "            grid[i][j] = 2\n",
    "            while q:\n",
    "                i, j = q.pop(0)\n",
    "                for x, y in ((1, 0), (-1, 0), (0, 1), (0, -1)):\n",
    "                    ni, nj = i+x, j+y\n",
    "                    if ni<0 or nj<0 or ni>m-1 or nj>n-1 or grid[ni][nj] != 0:\n",
    "                        continue\n",
    "                    q.append((ni, nj))\n",
    "                    grid[ni][nj] = 2\n",
    "        for i in range(m):\n",
    "            if grid[i][0] == 0:\n",
    "                bfs(i, 0)\n",
    "            if grid[i][n-1] == 0:\n",
    "                bfs(i, n-1)\n",
    "        for i in range(n):\n",
    "            if grid[0][i] == 0:\n",
    "                bfs(0, i)\n",
    "            if grid[m-1][i] == 0:\n",
    "                bfs(m-1, i)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    ans += 1\n",
    "                    bfs(i, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(grid, i, j):\n",
    "            m = len(grid)\n",
    "            n = len(grid[0])\n",
    "            dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]\n",
    "            if i<0 or j<0 or i>=m or j>=n:\n",
    "                return\n",
    "            if grid[i][j] == 1:\n",
    "                return\n",
    "            grid[i][j] = 1\n",
    "            for d in dirs:\n",
    "                new_i = i + d[0]\n",
    "                new_j = j + d[1]\n",
    "                dfs(grid, new_i, new_j)\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            dfs(grid, i, 0)\n",
    "            dfs(grid, i, n-1)\n",
    "\n",
    "        for j in range(n):\n",
    "            dfs(grid, 0, j)\n",
    "            dfs(grid, m-1, j)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res+=1\n",
    "                    dfs(grid, i,j )\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def process(x, y):\n",
    "            if x<0 or x>= row or y<0 or y>=col: return\n",
    "            if grid[x][y] != 0: return \n",
    "            \n",
    "            grid[x][y] = 2\n",
    "            process(x+1, y)\n",
    "            process(x-1, y)\n",
    "            process(x, y+1)\n",
    "            process(x, y-1)\n",
    "    \n",
    "        \n",
    "        # 先处理在边界上不应该被统计的 封闭岛\n",
    "        for j in range(col):\n",
    "            if grid[0][j] == 0:\n",
    "                process(0, j)\n",
    "            if grid[row-1][j] == 0:\n",
    "                process(row-1, j)\n",
    "        \n",
    "        for i in range(row):\n",
    "            if grid[i][0] == 0:\n",
    "                process(i, 0)\n",
    "            if grid[i][col-1] == 0:\n",
    "                process(i, col-1)\n",
    "\n",
    "        # 这里就是反着求岛屿问题\n",
    "        for i in range(1, row-1):\n",
    "            for j in range(1, col-1):\n",
    "                if grid[i][j] == 0:\n",
    "                    ans = ans+1\n",
    "                    process(i, j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        directions = [\n",
    "            [0, 1],\n",
    "            [0, -1],\n",
    "            [-1, 0],\n",
    "            [1, 0],\n",
    "        ]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            print(x,y)\n",
    "            if not (0<=x<len(grid) and 0<=y<len(grid[0])):\n",
    "                return\n",
    "            if grid[x][y] == 1:\n",
    "                return\n",
    "\n",
    "            grid[x][y] = 1\n",
    "            for d in directions:\n",
    "                x_nx = x + d[0]\n",
    "                y_nx = y + d[1]\n",
    "                dfs(x_nx, y_nx)\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            dfs(i, 0)\n",
    "            dfs(i, len(grid[0])-1)\n",
    "        for j in range(len(grid[0])):\n",
    "            dfs(0, j)\n",
    "            dfs(len(grid)-1, j)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    res += 1\n",
    "                    dfs(i, j)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = {i: i for i in range(n)}\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "        \n",
    "    def union_direct(self, x, y):\n",
    "        x_root, y_root = self.find(x), self.find(y)\n",
    "        if x_root != y_root:\n",
    "            if self.size[y_root] < self.size[x_root]:\n",
    "                self.parent[y_root] = x_root\n",
    "                self.size[x_root] += self.size[y_root]\n",
    "            else:\n",
    "                self.parent[x_root] = y_root\n",
    "                self.size[y_root] += self.size[x_root]\n",
    "            \n",
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n + 1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                if i == 0 or i == m - 1 or j == 0 or j == n - 1:\n",
    "                    uf.union_direct(k, m * n)\n",
    "                if grid[i][j] == 0:\n",
    "                    if i < m - 1 and grid[i+1][j] == 0:\n",
    "                        uf.union_direct(k, k+n)\n",
    "                    if j < n - 1 and grid[i][j+1] == 0:\n",
    "                        uf.union_direct(k, k+1)\n",
    "                    \n",
    "        ret = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                ret += grid[i][j] == 0 and uf.find(k) == k\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def closedIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        lands=set()\n",
    "        nrow,ncol=len(grid),len(grid[0])\n",
    "        for ir in range(nrow):\n",
    "            for ic in range(ncol):\n",
    "                if grid[ir][ic]==0:\n",
    "                    lands.add((ir,ic))\n",
    "        if len(lands)==0:\n",
    "            return 0\n",
    "        dirs=[(0,1),(0,-1),(1,0),(-1,0),]\n",
    "        stack=[]\n",
    "\n",
    "        res=0\n",
    "        while lands:\n",
    "            tmp = lands.pop()\n",
    "            stack.append(tmp)\n",
    "            flag=True\n",
    "            tnum=1\n",
    "            while stack:\n",
    "                tmp=stack.pop()\n",
    "                for dir in dirs:\n",
    "                    x,y=tmp[0]+dir[0],tmp[1]+dir[1]\n",
    "                    if not (0<=x<nrow and 0<=y<ncol):\n",
    "                        flag=False\n",
    "                        continue\n",
    "                    if (x,y) in lands:\n",
    "                        lands.remove((x,y))\n",
    "                        stack.append((x,y))\n",
    "                        tnum+=1\n",
    "            if flag:\n",
    "                res+=1\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
